package top100.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/26 14:04
 * @description:
 */
public class Solution763 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, i);// 更新为最后出现的位置
        }
        //记录轮询char的最大位置
        int idx = 0;//当前片段的结束索引
        int start = 0;//当前片段的起始索引
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //# 更新当前片段的结束索引为当前字母最后出现位置的最大值
            idx = Math.max(idx, map.get(c));
            //当遍历到当前片段的结束索引时，划分片段
            if (idx == i) {
                //计算片段长度并加入结果
                res.add(idx - start + 1);
                //更新下一个片段的起始索引
                start = idx + 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution763 solution = new Solution763();
        System.out.println(solution.partitionLabels("ababcbacadefegdehijhklij"));
        System.out.println(solution.partitionLabels("eccbbbbdec"));
    }
}
